/*
剑指 Offer II 012. 左右两边子数组的和相等
给你一个整数数组 nums ，请计算数组的 中心下标 。

数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。

如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。

如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1 。

 

示例 1：

输入：nums = [1,7,3,6,5,6]
输出：3
解释：
中心下标是 3 。
左侧数之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ，
右侧数之和 sum = nums[4] + nums[5] = 5 + 6 = 11 ，二者相等。
示例 2：

输入：nums = [1, 2, 3]
输出：-1
解释：
数组中不存在满足此条件的中心下标。
示例 3：

输入：nums = [2, 1, -1]
输出：0
解释：
中心下标是 0 。
左侧数之和 sum = 0 ，（下标 0 左侧不存在元素），
右侧数之和 sum = nums[1] + nums[2] = 1 + -1 = 0 。
 

提示：

1 <= nums.length <= 104
-1000 <= nums[i] <= 1000
 

注意：本题与主站 724 题相同： https://leetcode-cn.com/problems/find-pivot-index/
*/

#include<vector>
using namespace std;

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        int n = nums.size();
        vector<int> sums(n + 1);
        for(int i = 1; i <= n; ++i)
        {
            sums[i] = sums[i-1] + nums[i-1];
        }

        int pivotIndex = -1;
        for(int i = 0; i < n; ++i)
        {
            // sum 0...i - 1 == sum of i + 1 ... n - 1
            // i in the middle
            if(sums[i] == sums[n] - sums[i+1])
            {
                pivotIndex = i;
                break;
            }
        }

        return pivotIndex;
    }

    //similar to method 1,but use O(1) space 
    int pivotIndex(vector<int>& nums)
    {
        int n = nums.size();
        int total = 0;
        for(int i = 0; i < n; ++i)
        {
            total += nums[i];
        }

        int pivotIndex = -1;
        int sum = 0;
        for(int i = 0; i < n; ++i)
        {
            //left * 2 == total - current value
            //left  == right
            if(sum * 2 == total - nums[i])
            {
                return i;
            }
            sum += nums[i];
        }

        return pivotIndex;
    }
};

/*
1991. Find the Middle Index in Array
Easy

374

18

Add to List

Share
Given a 0-indexed integer array nums, find the leftmost middleIndex (i.e., the smallest amongst all the possible ones).

A middleIndex is an index where nums[0] + nums[1] + ... + nums[middleIndex-1] == nums[middleIndex+1] + nums[middleIndex+2] + ... + nums[nums.length-1].

If middleIndex == 0, the left side sum is considered to be 0. Similarly, if middleIndex == nums.length - 1, the right side sum is considered to be 0.

Return the leftmost middleIndex that satisfies the condition, or -1 if there is no such index.

 

Example 1:

Input: nums = [2,3,-1,8,4]
Output: 3
Explanation: The sum of the numbers before index 3 is: 2 + 3 + -1 = 4
The sum of the numbers after index 3 is: 4 = 4
Example 2:

Input: nums = [1,-1,4]
Output: 2
Explanation: The sum of the numbers before index 2 is: 1 + -1 = 0
The sum of the numbers after index 2 is: 0
Example 3:

Input: nums = [2,5]
Output: -1
Explanation: There is no valid middleIndex.
 

Constraints:

1 <= nums.length <= 100
-1000 <= nums[i] <= 1000
 

Note: This question is the same as 724: https://leetcode.com/problems/find-pivot-index/
*/

//本题同上面一题解法完全一致,只是说法不同
class Solution {
public:
    int findMiddleIndex(vector<int>& nums) {
        int n = nums.size();
        vector<int> sums(n + 1);
        for(int i = 1; i <= n; ++i)
        {
            sums[i] = sums[i-1] + nums[i-1];
        }

        int pivotIndex = -1;
        for(int i = 0; i < n; ++i)
        {
            // sum 0...i - 1 == sum of i + 1 ... n - 1
            // i in the middle
            if(sums[i] == sums[n] - sums[i+1])
            {
                pivotIndex = i;
                break;
            }
        }

        return pivotIndex;
    }
};
/*
1013. Partition Array Into Three Parts With Equal Sum
Easy

1079

118

Add to List

Share
Given an array of integers arr, return true if we can partition the array into three non-empty parts with equal sums.

Formally, we can partition the array if we can find indexes i + 1 < j with (arr[0] + arr[1] + ... + arr[i] == arr[i + 1] + arr[i + 2] + ... + arr[j - 1] == arr[j] + arr[j + 1] + ... + arr[arr.length - 1])

 

Example 1:

Input: arr = [0,2,1,-6,6,-7,9,1,2,0,1]
Output: true
Explanation: 0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1
Example 2:

Input: arr = [0,2,1,-6,6,7,9,-1,2,0,1]
Output: false
Example 3:

Input: arr = [3,3,6,5,-2,2,5,1,-9,4]
Output: true
Explanation: 3 + 3 = 6 = 5 - 2 + 2 + 5 + 1 - 9 + 4
 

Constraints:

3 <= arr.length <= 5 * 104
-104 <= arr[i] <= 104
Accepted
62,180
Submissions
139,380*/

class Solution {
public:
    bool canThreePartsEqualSum(vector<int>& arr) {
        int n = arr.size();
        vector<int> sums(n + 1);
        for(int i = 1; i <= n; ++i)
        {
            sums[i] = sums[i-1] + arr[i-1];
            // printf("i=%d,sums[%d]=%d\n",i,i,sums[i]);
        }
        
        if(sums[n] % 3 != 0)
        {
            return false;
        }
        
        int subSum = sums[n] / 3;
        
        //start from 1,ensure at least 1 element at start
        for(int i = 1;i < n; ++i)
        {
            if(sums[i] == subSum)
            {
                // < n,ensure at least 1 element in the 3rd part
                for(int j = i + 1; j < n; ++j)
                {
                    if(sums[j] - sums[i] == subSum && subSum == sums[n] - sums[j])
                    {
                        // printf("i=%d,j=%d,n=%d\n",i,j,n);
                        return true;
                    }
                }
            }

        }
        
        return false;
    }
};